package com.li.list;

import java.util.LinkedHashMap;

public class 删除链表中重复的节点 {
	public static void main(String[] args) {
		Node head = new Node();
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node66 = new Node(6);

		head.next = node1;
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		node6.next = node66;
		
		printList(head);
		deleteRepeat2(head);
		printList(head);
	}
	
	/**
	 * 删除链表中重复的节点----采用了java的linkedHashMap来去重和记录顺序
	 * @param head
	 * @return
	 */
	public static Node deleteRepeat(Node head){
		if(head == null || head.next == null){
			return head;
		}
		LinkedHashMap<Integer, Node> map = new LinkedHashMap<Integer, Node>();
		Node node = head;
		while((node = node.next)!=null){
			map.put(node.value, node);
		}
		Node pre = head;
		for(Node n : map.values()){
			pre.next = n;
			pre = n;
		}
		pre.next = null;
		return head;
	}
	
	/**
	 * 删除链表中重复的节点
	 * @param head
	 * @return
	 */
	public static Node deleteRepeat2(Node head){
		if(head == null || head.next == null){
			return head;
		}
		Node node = head.next;
		Node temp = null;
		while(node!=null){
			temp = node;
			while(temp!=null && temp.next!=null){
				if(node.value == temp.next.value){
					temp.next = temp.next.next;
				}
				temp = temp.next;
			}
			node = node.next;
		}
		return head;
	}
	
	/**
	 * 打印链表
	 * @param head
	 */
	public static void printList(Node head){
		while((head = head.next)!=null){
			System.out.print(head.value+" ");
		}
		System.out.println();
	}
}
